public class Solution9 {
    //879. 盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        //   int len = group.length;
        //   int MOD = (int)1e9 + 7;
        //   int[][][] dp = new int[len+1][n+1][minProfit+1];
        //dp[i][j][k] 表示 从前i个工作中选，员工不大于j,且利润至少为k，有多少种盈利计划
        //   for (int i = 0; i < n+1; i++) {
        //        dp[0][i][0] = 1;
        //   }
        //   for (int i = 1; i < len+1; i++) {
        //       for (int j = 0; j <= n; j++) {
        //         for (int k = 0; k <= minProfit; k++) {
        //             dp[i][j][k] += dp[i-1][j][k];
        //             if (j >= group[i-1] ) {
        //                dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
        //             }
        //             dp[i][j][k] %= MOD;
        //         }
        //       }
        //   }
        //   return dp[len][n][minProfit];

        //滚动数组优化版本
        int len = group.length;
        int MOD = (int)1e9 + 7;
        int[][] dp = new int[n+1][minProfit+1];

        for (int i = 0; i < n+1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < len+1; i++) {
            for (int j = n; j >= 0; j--) {
                for (int k = minProfit; k >= 0; k--) {

                    if (j >= group[i-1] ) {
                        dp[j][k] += dp[j-group[i-1]][Math.max(0,k-profit[i-1])];
                    }
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
}
